A. Field of the Invention
The present invention relates generally to routing systems and, more particularly, to systems and methods for performing cyclic redundancy checks on data transmitted in a communication system.
B. Description of Related Art
Cyclic Redundancy Checking (CRC) ensures the accuracy of frames transmitted between devices in a frame relay network. In practice, an originating device generates a CRC value based on the content of the frame to be transmitted and transmits the CRC value with the frame. A destination device compares the received CRC value to a recomputed CRC value to determine whether the frame was received correctly.
Several approaches exist for generating and checking CRCs. One such approach is described in Section C of RFC1662, xe2x80x9cPPP in HDLC-like Framing,xe2x80x9d July 1994, pp. 18-24. As described therein, the fast Frame Check Sequence (FCS) implementation requires successive iterations (16 for a 16 bit FCS, 32 for a 32 bit FCS) over the following loops:
Fcs=(fcs greater than  greater than 8){circumflex over ( )}fcstab_16[(fcs{circumflex over ( )}(*cp++)and 0xff) . . . for FCS16
Fcs=(fcs greater than  greater than 8){circumflex over ( )}fcstab_32[(fcs{circumflex over ( )}(*cp++)and 0xff) . . . for FCS32
where a memory access to an FCS lookup table (fcstab_16 and fcstab_32, respectively) is required for each loop. It will be appreciated that such an approach is inappropriate for extremely high performance applications (e.g., OC192) due to its iterative nature and concomitant memory accesses.
In high performance applications, conventional CRC generating and checking approaches face several problems. A first problem is speed. Typically, high performance routers require line rate performance (i.e., bits are processed as they arrive off the wire). The ability to calculate a CRC checksum in a single clock cycle is highly desirable to meeting this design goal.
A second problem is data width. For a given clock rate, the wider the checksum that can be calculated, the higher the line rate that can be supported. As such, high performance routers need the ability to handle wide input data (e.g., 128 bits for OC192 applications). Moreover, since the CRC check can occur over all, some, or none of the bits in an incoming bit stream, high performance routers need the ability to perform the CRC on a bit stream having an arbitrary number of invalid bits.
Therefore, there exists a need for systems and methods that improve CRC operations in a high performance environment.
Systems and methods, consistent with the present invention, address this and other needs by providing a cyclic redundancy checker/generator capable of performing a CRC operation in single cycle on data having wide width and an arbitrary number of invalid bits.
In accordance with the purpose of the invention as embodied and broadly described herein, a method for updating a cyclic redundancy check (CRC) value includes receiving data containing valid and invalid portions. The valid portions are positioned adjacent to one another. The method also receives first information representing the number of valid portions in the data and second information representing a current CRC value. The method determines the updated CRC value based on the data, first information, and second information.
In another implementation consistent with the present invention, a CRC includes a plurality of CRC units and at least one multiplexer. The CRC units receive data, containing valid and invalid portions, the valid portions being adjacent to one another, and a current CRC value, and generate CRC outputs based on the received data and current CRC value. The multiplexer receives the CRC outputs and information representing a number of valid portions in the received data, and outputs one of the received CRC outputs based on the information.
In yet another implementation consistent with the present invention, a CRC includes a first input port, a second input port, a third input port, CRC logic, and an output port. The first input port receives first data to be added to a current CRC value. The first data contains valid and invalid portions, where the valid portions are adjacent to one another. The second input port receives second data representing a number of valid portions in the first data. The third input port receives the current CRC value. The CRC logic is coupled to the first, second and third ports and configured to generate an updated CRC value based on the first data, second data, and current CRC value. The output port is coupled to the CRC logic and configured to output the updated CRC value.
In still another implementation consistent with the present invention, a network device includes a routing engine and a packet forwarding engine. The routing engine maintains one or more routing tables and a forwarding table. The packet forwarding engine includes a CRC and a transmitter. The CRC receives a packet having valid portions and invalid portions, the valid portions being adjacent, receives a signal representing a number of valid portions in the packet, receives a current CRC value, and determines an updated CRC value based on the received packet, signal, and current CRC value. The transmitter appends the updated CRC value to the packet and transmits the packet.
In still another implementation consistent with the present invention, a method for updating a CRC value is disclosed. The method includes receiving data containing an arbitrary number of valid and invalid portions, the valid portions being positioned adjacent to one another; receiving a signal representing a quantity of valid portions in the data; receiving a current CRC value; and updating the current CRC value using the data and signal in a single clock cycle.